Traditional real-time video streaming (e.g., for live media streaming and/or real-time communications) requires a regular pattern of key-frames to provide random access to the stream. Random access is necessary to (1) allow new clients to join the stream, (2) allow clients experiencing technical difficulties to re-enter the stream, and/or (3) allow clients to jump backward or forward within the stream. However, due to the large size of key-frames, traditional real-time video streams require a large amount of network bandwidth, which may disrupt network behavior and latency. Some strategies for responding to the large bandwidth required by traditional real-time video streams is to compensate for the size of key-frames by reducing the size of other frames (e.g., p-frames and/or b-frames) within a stream. However, this may reduce the overall quality (e.g., video quality) of a real-time video stream. The instant disclosure therefore identifies a need for improved systems and methods for allowing random access to real-time video streams with minimal use of key-frames.